#include "helper/HPQueue.h"
#include "helper/APQueue.h"
#include "Graph.h"

//using namespace std;

void print_path(Graph& G, vector<Vertex*> p, Vertex* s, Vertex* v)
{
	if (v == s) cout << s->getID() << " ";
	else if (p[v->getID()-1] == NULL ) cout << "No path from " << s->getID() << " to " << v->getID() << " exists.";
	else{
		print_path(G, p, s, p[v->getID()-1]);
		cout << v->getID() << ' ';
	}
}

void dijkstra(Graph& graph, /*unsigned int source, unsigned int dest,*/ HPQueue<Vertex*> q)
{
	int comp_in, comp_rm, comp_up;
	comp_in = comp_rm = comp_up = 0;
	cout << "Heap Based:\n";
	const vector<Vertex*>& V = graph.get_vertices();
	vector<int> d(V.size()); //array of current shortest distance for each vertex
	vector<Vertex*> p(V.size()); //array of current parent for each vertex
	vector<int*> pos(V.size());
	for (int i = 0; i < V.size(); i++)
	{	
		d[i] = 65535;
		p[i] = NULL;
	}
	d[0] = 0; //may need to change to source

	for (int i = 0; i < V.size(); i++)
	{
		const unsigned int id = V[i]->getID();
		pos[i] = q.insert_item(d[i],V[i],comp_in);
	}
	while (!q.empty())
	{
		Vertex* u = q.min_elem();
		q.remove_min(comp_rm);
		vector<Edge>& ol = u->get_ol();
		for (int i = 0; i < ol.size(); i++){
			
			int w = ol[i].getWeight();
			Vertex* v = ol[i].geteVertP();
			
			if (d[v->getID()-1]>d[u->getID()-1]+w) //w is the weight of the edge between u and v
			{
				d[v->getID()-1]=d[u->getID()-1]+w;
				p[v->getID()-1] = u;
				q.update_key(pos[v->getID()-1], d[v->getID()-1], comp_up);
			}
			//cout << d[v->getID()-1] << '\n';
		}
	}
	//print_path(graph,,)
	cout << "Distance: " << '\t' << "Path:" << '\n';
	for (int i = 0; i < d.size(); i++) //print edges
	{
		cout << d[i] << '\t';
		print_path(graph,p,V[0],V[i]);
		cout << '\n';
	}
	cout << "Insertion comparisons: " << comp_in << '\n'
		<< "Removal comparisons: " << comp_rm << '\n'
		<< "Update key comparions: " << comp_up << '\n';
}

void dijkstra(Graph& graph, /*unsigned int source, unsigned int dest,*/ APQueue<Vertex*> q) //http:www.codeproject.com/Articles/24816/A-Fast-Priority-Queue-Implementation-of-the-Dijkst
{
	int comp_in, comp_rm, comp_up;
	comp_in = comp_rm = comp_up = 0;
	cout << "\nArray Based (unsorted):\n";
	const vector<Vertex*>& V = graph.get_vertices();
	vector<int> d(V.size()); //array of current shortest distance for each vertex
	vector<Vertex*> p(V.size()); //array of current parent for each vertex
	vector<int*> pos(V.size());
	for (int i = 0; i < V.size(); i++)
	{	
		d[i] = 65535;
		p[i] = NULL;
	}
	d[0] = 0; //may need to change to source
	
	for (int i = 0; i < V.size(); i++)
	{
	    unsigned int id = V[i]->getID();
		pos[i] = q.insert_item(d[i],V[i],comp_in);
	}
	while (!q.empty())
	{
		Vertex* u = q.min_elem();
		q.remove_min(comp_rm);
		vector<Edge>& ol = u->get_ol();
		for (int i = 0; i < ol.size(); i++){
			
			int w = ol[i].getWeight();
			Vertex* v = ol[i].geteVertP();
			
			if (d[v->getID()-1]>d[u->getID()-1]+w) //w is the weight of the edge between u and v
			{
				d[v->getID()-1]=d[u->getID()-1]+w; //swap
				p[v->getID()-1] = u;
				q.update_key(pos[v->getID()-1], d[v->getID()-1], comp_up); //update
			}
			//cout << d[v->getID()-1] << '\n';
		}
	}
	//print_path(graph,,)
	cout << "Distance: " << '\t' << "Path:" << '\n';
	for (int i = 0; i < d.size(); i++) //print edges
	{
		cout << d[i] << '\t';
		print_path(graph,p,V[0],V[i]);
		cout << '\n';
	}
	cout << '\n';
	cout << "Insertion comparisons: " << comp_in << '\n'
		<< "Removal comparisons: " << comp_rm << '\n'
		<< "Update key comparions: " << comp_up << '\n';
}

int main()
{
	//cout << "Enter filename: ";
	string str;
	str = "data/graph256.txt";
	//cin >> str;
	Graph graph(str);
	
	int a_cmps = 0;
	int h_cmps = 0;
	unsigned int source = 0;
	unsigned int dest = 0;
	
	//convert uint to vertex here
	
	APQueue<Vertex*> ap;
	HPQueue<Vertex*> hp;
	
	//const vector<Vertex*>& v = graph.get_vertices(); //array of vertex pointers
	
	dijkstra(graph, hp);
	dijkstra(graph, ap);
}
